package com.algrithom.stack.monotonousstack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Stack;

public class Solution4 {
    
    public static void main(String[] args){
        char[][] matrix = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
        Solution4 solution4 = new Solution4();
        System.out.println(solution4.maximalRectangle(matrix));
    }
    
    public int largestRectangleArea(int[] heights){
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        int[] copy = new int[heights.length + 2];
        System.arraycopy(heights,0,copy,1,heights.length);
        for (int i = 0; i < copy.length; i++) {
            while (!stack.isEmpty() && copy[stack.peek()] > copy[i]) {
                int idx = stack.pop();
                // i - stack.peek() -1 :由于copy在原来基础上加了两个列，取i 和 stack.peek() + 1之间的数据 
                res = Math.max(res,(i - stack.peek() - 1) * copy[idx]);
            }
            stack.push(i);
        }
        return res;
    }
    
    public int maximalRectangle(char[][] matrix){
        if (matrix.length == 0) {
            return 0;
        }
        int res = 0;
        int[] dp = new int[matrix[0].length];
        for (char[] chars : matrix) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (chars[j] == '1') {
                    dp[j] += 1;
                } else {
                    dp[j] = 0;
                }
            }
            res = Math.max(res,largestRectangleArea(dp));
        }
        return res;
    }
    
    public int maximalRectangle2(char[][] matrix){
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int col = matrix[0].length;
        int[] height = new int[col + 2];
        int res = 0;
        for (char[] chars : matrix) {
            Deque<Integer> stack = new ArrayDeque<>();
            for (int j = 0; j < col + 2; j++) {
                if (j >= 1 && j <= col) {
                    if (chars[j - 1] == '1') {
                        height[j] += 1;
                    } else {
                        height[j] = 0;
                    }
                }
                while (!stack.isEmpty() && height[stack.peek()] > height[j]) {
                    int cur = stack.pop();
                    res = Math.max(res,(j - stack.peek() - 1) * height[cur]);
                }
                stack.push(j);
            }
        }
        return res;
    }
    
    public int maximalRectangle3(char[][] matrix){
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int[] leftJ = new int[col];
        Arrays.fill(leftJ,-1);
        
        int[] rightJ = new int[col];
        Arrays.fill(rightJ,col);
        
        int[] heightJ = new int[col];
        
        int res = 0;
        for (int i = 0; i < row; i++) {
            int curLeft = -1;
            int curRight = col;
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    heightJ[j] += 1;
                } else {
                    heightJ[j] = 0;
                }
            }
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    leftJ[j] = Math.max(leftJ[j],curLeft);
                } else {
                    leftJ[j] = -1;
                    curLeft = j;
                }
            }
            for (int j = col - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    rightJ[j] = Math.min(rightJ[j],curRight);
                } else {
                    rightJ[j] = col;
                    curRight = j;
                }
            }
            for (int j = 0; j < col; j++) {
                res = Math.max(res,(rightJ[j] - leftJ[j] - 1) * heightJ[j]);
            }
        }
        return res;
    }
}
